Dvoretzky–Kiefer–Wolfowitz inequality

In the theory of probability and statistics, the Dvoretzky–Kiefer–Wolfowitz inequality predicts how close an empirically determined distribution function will be to the distribution function from which the empirical samples are drawn. It is named after Aryeh Dvoretzky, Jack Kiefer, and Jacob Wolfowitz, who in 1956 proved[1] the inequality with a unspecified multiplicative constant C in front of the exponent on the right-hand side. In 1990, Pascal Massart proved the inequality with the sharp constant C = 1, [2] confirming a conjecture due to Birnbaum and McCarty.[3]

The DKW inequality

Given a natural number n, let X1, X2, …, Xn be real-valued independent and identically distributed random variables with distribution function F(·). Let Fn denote the associated empirical distribution function defined by

F_n(x) = \frac1n \sum_{i=1}^n \mathbf{1}_{\{X_i\leq x\}},\qquad x\in\mathbb{R}.

The Dvoretzky–Kiefer–Wolfowitz inequality bounds the probability that the random function Fn differs from F by more than a given constant ε > 0 anywhere on the real line. More precisely, there is the one-sided estimate

\Pr\Bigl(\sup_{x\in\mathbb R} \bigl(F_n(x) - F(x)\bigr) > \varepsilon \Bigr) \le e^{-2n\varepsilon^2}\qquad \text{for every }\varepsilon\geq\sqrt{\tfrac{1}{2n}\ln2},

which also implies a two-sided estimate

\Pr\Bigl(\sup_{x\in\mathbb R} |F_n(x) - F(x)| > \varepsilon \Bigr) \le 2e^{-2n\varepsilon^2}\qquad \text{for every }\varepsilon>0.

This strengthens the Glivenko–Cantelli theorem by quantifying the rate of convergence as n tends to infinity. It also estimates the tail probability of the Kolmogorov–Smirnov statistic. The inequalities above follow from the case where F corresponds to be the uniform distribution on [0,1] in view of the fact[4] that Fn has the same distributions as Gn(F) where Gn is the empirical distribution of U1, U2, …, Un where these are independendent and Uniform(0,1), and noting that

\sup_{x\in\mathbb R} |F_n(x) - F(x)|\stackrel{d}{=} \sup_{x \in \mathbb R} | G_n (F(x)) - F(x) | \le \sup_{0 \le t \le 1} | G_n (t) -t | ,

with equality if and only if F is continuous.

References

  1. ^ Dvoretzky, A.; Kiefer, J.; Wolfowitz, J. (1956), "Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator", Annals of Mathematical Statistics 27 (3): 642–669, doi:10.1214/aoms/1177728174, MR0083864, http://projecteuclid.org/euclid.aoms/1177728174 
  2. ^ Massart, P. (1990), "The tight constant in the Dvoretzky–Kiefer–Wolfowitz inequality", The Annals of Probability 18 (3): 1269–1283, doi:10.1214/aop/1176990746, MR1062069, http://projecteuclid.org/euclid.aop/1176990746 
  3. ^ Birnbaum, Z. W.; McCarty, R. C. (1958). "A distribution-free upper confidence bound for Pr{Y<X}, based on independent samples of X and Y". Ann. Math. Statist. 29: 558–562. doi:10.1214/aoms/1177706631. MR0093874. Zbl 0087.34002. http://projecteuclid.org/euclid.aoms/1177706631. 
  4. ^ Shorack, G.R.; Wellner, J.A. (1986), Empirical Processes with Applications to Statistics, Wiley, ISBN 0-471-86725-X